Scene reconstruction involves building three-dimensional, computer models of scenes, given several two-dimensional images or photographs of the scenes. In order to create the models, reconstruction algorithms are typically used. However, these algorithms need a rule or a set of rules to determine where the surfaces and regions shown in the photographs should be represented in the three-dimensional models.
One rule that can be used for building three-dimensional models from two-dimensional images is based on color consistency. However, in order for the color consistency rule to be successfully applied, the surfaces of the scene should be Lambertian. In other words, the surfaces should reflect light equally in all directions, or at least nearly so. In particular, it is preferable that the surfaces not be shiny or mirrored.
FIG. 1A illustrates a point 10 on a surface 20 of a scene 30 that is being imaged or photographed by a first camera 40 and a second camera 50. The cameras 40, 50 are at different angles relative to the surface 20. As shown in FIG. 1A, the point 10 on the surface 20 will appear to have consistent (i.e., similar) color from every image or photograph that includes it, regardless of the angle from which the image is taken. In other words, the point 10 will have the same color in a first image taken by the first camera 40 and in a second image taken by the second camera 50, even though the camera angle is different.
In contrast, FIG. 1B illustrates two cameras 40, 50 taking images of a point 15 that is not on the surface 20 of the scene 30. Since each of the cameras 40, 50 has an unoccluded view of other surfaces 60, 70 beyond the point 15, and since the other surfaces 60, 70 beyond the point 15 will, in general, have inconsistent colors, there will not be any color consistency of the images at the point 15 in question. Therefore, surface points 10 and non-surface points 15 can be distinguished based on the color consistency of the points from image to image. Then, based on where surface points are present, the locations of the surfaces of the scene can be determined and three-dimensional models can be formed.
Reconstruction of a three-dimensional model from two-dimensional images is typically simplified by assuming that the images are calibrated. This means that various camera parameters, including camera position and orientation, are known and that, given a point in the three-dimensional scene, it can be determined where the point will appear in the photographs. If color images of the scene are obtained by some means other than photography, those images can be used in place of photographs for reconstructing the scene.
Once the locations of the surfaces of the scene have been determined, the surfaces can be three-dimensionally modeled using voxels or other modeling primitives such as polygons. Voxels, which are three-dimensional volume elements analogous to two-dimensional pixels, can be thought of as tiny cubes that typically occur on a regular grid. As voxels get smaller and smaller, they approximate points.
In model building, voxels or other modeling primitives can be opaque to represent a surface of the scene. They can also be transparent to represent air or space that is not occupied by any surface or, if it has not yet been determined whether the voxels are part of the surface, the voxels can be left in an undefined state that signifies that a final determination concerning the voxel has not yet been made.
The reconstruction algorithms based on color consistency typically test a large number of voxels or other primitives at specific locations to build a model. If the voxels or other primitives are found to have consistent color in the photographs, they are added to the model. On the other hand, if they are found to be inconsistent, the voxels or other primitives are removed from the model. Voxels that are in the undefined state described above are generally technically neither added nor removed from the model. Instead, they are simply not used until their color consistency can be determined.
Typically, the two-dimensional images or photographs used in scene reconstruction are either captured as digital images, using a digital camera, or taken with a conventional film camera and then digitized using a scanner. The digital images are typically composed of rows and columns of picture elements, pixels, or other image partitions that each have a color. Based on the color of the image partition, a number or an array of numbers can be assigned to the pixel.
Many different schemes, called color spaces, are used to encode pixel color. Many of these color spaces have multiple dimensions. For example, the Red-Green-Blue (RGB) color space has three dimensions: red, green, and blue, and each color is assigned a numerical array value based on the amount of red, green, and blue that is contained in the color of the pixel. For example, a color that is 10% red, 33% green, and 57% blue could be assigned an array value of (10, 33, 57) while a color that is 100% green could be assigned the (0, 100, 0) array value.
Unlike dimensionless points, voxels and other primitives have nonzero size and, if they are visible from one of the photographs, they are generally visible from a number of pixels in the photographs. Hence, if V is a voxel or other modeling primitive and i is a photograph, then SV,i is the subset of image partitions or pixels in i from which V is visible. SV,i can also be called the visibility set of primitive V in photograph i.
In modeling methods that make use of color consistency, a voxel or other modeling primitive is considered to be color consistent if all of its visibility sets are of a consistent color. However, pixels and visibility sets have been defined as having a consistent color in a number of different ways according to the related art. Hence, there is ambiguity in the related art concerning color consistency rules.
According to some related art methods, given a number, n, of pixels with colors of numerical value, xi, their mean color, μ, can be computed as:
      μ    =          (                                                  ∑                              i                =                0                                            n                -                1                                      ⁢                                                  ⁢                          x              red              i                                n                ,                                            ∑                              i                =                0                                            n                -                1                                      ⁢                                                  ⁢                          x              green              i                                n                ,                                            ∑                              i                =                0                                            n                -                1                                      ⁢                                                  ⁢                          x              blue              i                                n                    )        ,and the color variance, σ2, of the pixels can be computed as
      σ    2    =            1      n        ⁢                  ∑                  i          =          0                          n          -          1                    ⁢                          ⁢                        (                                                    (                                                      x                    red                    i                                    -                                      μ                    red                                                  )                            2                        +                                          (                                                      x                    green                    i                                    -                                      μ                    green                                                  )                            2                        +                                          (                                                      x                    blue                    i                                    -                                      μ                    blue                                                  )                            2                                )                .            The standard deviation of color of the pixels can then be computed as σ, the square root of the variance.
It is known in the related art to use monochrome images rather than color images to construct a three-dimensional model. When monochrome images are used, each shade of gray is assigned a different numerical value. Then, if a voxel is visible from two pixels whose gray values differ by more than some threshold (typically 10–15), the voxels are considered to have inconsistent color.
When the color consistency of a voxel V is tested according to some related art methods, the visibility sets of V in each image are computed only approximately. Rather than finding the true projection of V into an image, some related art methods simplify the computation by assuming the projection will be a square of an appropriate size.
According to these methods, the first step in computing the color consistency of V is to find the set S of pixels that is the union of all the pixels in all such squares. Then the method computes the variance, σ2, and the likelihood ratio test, λV, of S, wherein λV is defined as (n−1)σ2 when S consists of n pixels. Finally, some of these methods consider the voxel to be color consistent if λV is less than some experimentally-found threshold that yields the best three-dimensional model.
According to yet other methods, when the color consistency of a voxel V is tested, the voxel's visibility sets (the SV,i's) are first found in each of the images analyzed. Then, the mean color μi of each non-empty SV,i s found. When there are m such SV,i, then the likelihood ratio test λV, defined as (m−1)σ2, of the m mean colors is computed.
According to these methods, the λV is computed over a different number of colors than in the methods previously discussed. Namely, the ratio test is now computed over the number of images from which V is visible rather than over the number of pixels from which V is visible. Finally, like in the other methods, the voxel is considered to be color consistent if λV is less than some experimentally-found threshold.
In some methods, the color consistency of a voxel V is computed by first finding the visibility sets of V for all of the images. Then, the variance of the union of the visibility sets is computed. According to these methods, the voxel is considered to be color consistent if the variance is less than some threshold that is found experimentally.
Yet other methods begins their voxel color consistency computations by first finding the visibility sets of the voxel (the SV,i's) for all the images. Then, the mean color μi of each non-empty SV,i is computed. At that point, for every pair μi and μj of such means, the L1 norm of μi and μj, is computed, wherein the L1 norm is defined as:normi,j=(|μi red−μj red|+|μi green−μj green|+|μi blue−μj blue|).If the maximum of these norms is less than a threshold that is determined experimentally, then the voxel is considered to be color consistent.
As shown above, related art color consistency measures all rely on experimentally determined threshold values. In order to set the threshold values, many reconstructions are performed using different thresholds and the best model is kept. Since each reconstruction takes considerable time, this process is very tedious. Furthermore, one threshold value sometimes works best on one part of a scene while a different threshold value works best elsewhere. Hence, there may be no single best threshold value. The histogram-based consistency measures of the present invention do not use a threshold and thereby eliminate these problems.
The related art has also made use of color histograms, which are a well known statistical device. However, color histograms have never been used for color consistency testing in scene reconstruction. Rather, color histograms have generally been used for indexing in databases of images. Specifically, given a color histogram, images with similar color histograms are retrieved from the database.
Another application of histograms has been in image segmentation. In these applications, regions of an image with similarly-colored histograms are identified. Histogram-based image segmentation has been useful in medical imaging.